package com.michael.tree.btree.demo;

public class BTreeNode {
    int[] keys;  // An array of keys
    int t;      // Minimum degree (defines the range for number of keys)
    BTreeNode[] c; // An array of child pointers
    int n;     // current number of keys
    boolean leaf; // Is true when node is leaf. Otherwise false

    public BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        keys = new int[2 * t - 1];
        c = new BTreeNode[2*  t];
        n = 0;
    }

    void traverse(){
        // There are n keys and n+1 children, traverse through n keys
        // and first n children
        int i;
        for (i = 0; i < n; i++)
        {
            // If this is not leaf, then before printing key[i],
            // traverse the subtree rooted with child c[i].
            if (leaf == false)
                c[i].traverse();
            System.out.print(" " + keys[i]);
        }
//        System.out.println("");
        // Print the subtree rooted with last child
        if (leaf == false)
            c[i].traverse();
    }

    BTreeNode search(int k){
        // Find the first key greater than or equal to k
        int i = 0;
        while (i < n && k > keys[i])
            i++;

        // If the found key is equal to k, return this node
        if (keys[i] == k)
            return this;

        // If key is not found here and this is a leaf node
        if (leaf == true)
            return null;

        // Go to the appropriate child
        return c[i].search(k);
    }

    int findKey(int k) {
        int idx = 0;
        while (idx < n && keys[idx] < k)
            ++idx;
        return idx;
    }

    void insertNonFull(int k){
        // Initialize index as index of rightmost element
        int i = n-1;

        // If this is a leaf node
        if (leaf == true)
        {
            // The following loop does two things
            // a) Finds the location of new key to be inserted
            // b) Moves all greater keys to one place ahead
            while (i >= 0 && keys[i] > k)
            {
                keys[i+1] = keys[i];
                i--;
            }

            // Insert the new key at found location
            keys[i+1] = k;
            n = n+1;
        }
        else // If this node is not leaf
        {
            // Find the child which is going to have the new key
            while (i >= 0 && keys[i] > k)
                i--;

            // See if the found child is full
            if (c[i+1].n == 2*t-1)
            {
                // If the child is full, then split it
                splitchild(i+1, c[i+1]);

                // After split, the middle key of c[i] goes up and
                // c[i] is splitted into two.  See which of the two
                // is going to have the new key
                if (keys[i+1] < k)
                    i++;
            }
            c[i+1].insertNonFull(k);
        }
    }

    void splitchild(int i, BTreeNode y){
        // create a new node which is going to store (t-1) keys
        // of y
        BTreeNode z = new BTreeNode(y.t, y.leaf);
        z.n = t - 1;

        // copy the last (t-1) keys of y to z
        for (int j = 0; j < t-1; j++)
            z.keys[j] = y.keys[j+t];

        // copy the last t children of y to z
        if (y.leaf == false)
        {
            for (int j = 0; j < t; j++)
                z.c[j] = y.c[j+t];
        }

        // Reduce the number of keys in y
        y.n = t - 1;

        // Since this node is going to have a new child,
        // create space of new child
        for (int j = n; j >= i+1; j--)
            c[j+1] = c[j];

        // Link the new child to this node
        c[i+1] = z;

        // A key of y will move to this node. Find location of
        // new key and move all greater keys one space ahead
        for (int j = n-1; j >= i; j--)
            keys[j+1] = keys[j];

        // copy the middle key of y to this node
        keys[i] = y.keys[t-1];

        // Increment count of keys in this node
        n = n + 1;
    }

    void remove(int k) {
        int idx = findKey(k);

        // The key to be removed is present in this node
        if (idx < n && keys[idx] == k) {

            // If the node is a leaf node - removeFromLeaf is called
            // Otherwise, removeFromNonLeaf function is called
            if (leaf)
                removeFromLeaf(idx);
            else
                removeFromNonLeaf(idx);
        } else {

            // If this node is a leaf node, then the key is not present in tree
            if (leaf) {
                System.out.println("The key " + k + " is does not exist in the tree");
                return;
            }

            // The key to be removed is present in the sub-tree rooted with this node
            // The flag indicates whether the key is present in the sub-tree rooted
            // with the last child of this node
            boolean flag = ((idx == n) ? true : false);

            // If the child where the key is supposed to exist has less that t keys,
            // we fill that child
            if (c[idx].n < t)
                fill(idx);

            // If the last child has been merged, it must have merged with the previous
            // child and so we recurse on the (idx-1)th child. Else, we recurse on the
            // (idx)th child which now has atleast t keys
            if (flag && idx > n)
                c[idx - 1].remove(k);
            else
                c[idx].remove(k);
        }
        return;
    }

    void removeFromLeaf(int idx) {
        for (int i = idx + 1; i < n; ++i)
            keys[i - 1] = keys[i];

        // Reduce the count of keys
        n--;
        return;
    }

    void removeFromNonLeaf(int idx) {
        int k = keys[idx];
        if (c[idx].n >= t) {
            int pred = getPred(idx);
            keys[idx] = pred;
            c[idx].remove(pred);
        } else if (c[idx + 1].n >= t) {
            int succ = getSucc(idx);
            keys[idx] = succ;
            c[idx + 1].remove(succ);
        } else {
            merge(idx);
            c[idx].remove(k);
        }
        return;
    }

    int getPred(int idx) {
        BTreeNode cur = c[idx];
        while (!cur.leaf)
            cur = cur.c[cur.n];

        // Return the last key of the leaf
        return cur.keys[cur.n - 1];
    }

    int getSucc(int idx) {
        BTreeNode cur = c[idx + 1];
        while (!cur.leaf)
            cur = cur.c[0];

        // Return the first key of the leaf
        return cur.keys[0];
    }

    void fill(int idx) {
        if (idx != 0 && c[idx - 1].n >= t)
            borrowFromPrev(idx);
        else if (idx != n && c[idx + 1].n >= t)
            borrowFromNext(idx);
        else {
            if (idx != n)
                merge(idx);
            else
                merge(idx - 1);
        }
        return;
    }

    void borrowFromPrev(int idx){
        BTreeNode child=c[idx];
        BTreeNode sibling=c[idx-1];

        for (int i=child.n-1; i>=0; --i)
            child.keys[i+1] = child.keys[i];

        if (!child.leaf)
        {
            for(int i=child.n; i>=0; --i)
                child.c[i+1] = child.c[i];
        }

        child.keys[0] = keys[idx-1];

        if(!child.leaf)
            child.c[0] = sibling.c[sibling.n];

        keys[idx-1] = sibling.keys[sibling.n-1];

        child.n += 1;
        sibling.n -= 1;

        return;
    }

    void borrowFromNext(int idx){
        BTreeNode child=c[idx];
        BTreeNode sibling=c[idx+1];

        // keys[idx] is inserted as the last key in c[idx]
        child.keys[(child.n)] = keys[idx];

        // Sibling's first child is inserted as the last child
        // into c[idx]
        if (!(child.leaf))
            child.c[(child.n)+1] = sibling.c[0];

        //The first key from sibling is inserted into keys[idx]
        keys[idx] = sibling.keys[0];

        // Moving all keys in sibling one step behind
        for (int i=1; i<sibling.n; ++i)
            sibling.keys[i-1] = sibling.keys[i];

        // Moving the child pointers one step behind
        if (!sibling.leaf)
        {
            for(int i=1; i<=sibling.n; ++i)
                sibling.c[i-1] = sibling.c[i];
        }

        // Increasing and decreasing the key count of c[idx] and c[idx+1]
        // respectively
        child.n += 1;
        sibling.n -= 1;

        return;
    }

    void merge(int idx){
        BTreeNode child = c[idx];
        BTreeNode sibling = c[idx+1];

        // Pulling a key from the current node and inserting it into (t-1)th
        // position of c[idx]
        child.keys[t-1] = keys[idx];

        // copying the keys from c[idx+1] to c[idx] at the end
        for (int i=0; i<sibling.n; ++i)
            child.keys[i+t] = sibling.keys[i];

        // copying the child pointers from c[idx+1] to c[idx]
        if (!child.leaf)
        {
            for(int i=0; i<=sibling.n; ++i)
                child.c[i+t] = sibling.c[i];
        }

        // Moving all keys after idx in the current node one step before -
        // to fill the gap created by moving keys[idx] to c[idx]
        for (int i=idx+1; i<n; ++i)
            keys[i-1] = keys[i];

        // Moving the child pointers after (idx+1) in the current node one
        // step before
        for (int i=idx+2; i<=n; ++i)
            c[i-1] = c[i];

        // Updating the key count of child and the current node
        child.n += sibling.n+1;
        n--;

        // Freeing the memory occupied by sibling
        sibling = null;
        return;
    }
}
